﻿#pragma warning(disable:4267)
#pragma warning(disable:4996)
#pragma warning(disable:6031)
#pragma warning(disable:6011)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

namespace Y190713_Graph {
	int main();


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

	/* ---------------- 基于链表的 栈,队列 ---------------- */
	typedef int ElementType;
	const ElementType ErrorData = -999999;
	typedef struct LNode* LinkList;
	struct LNode {
		ElementType data;
		LinkList next;
	};

	typedef struct StackStruct* Stack;
	struct StackStruct {
		LinkList head;
	};

	typedef struct QueueStruct* Queue;
	struct QueueStruct {
		LinkList front;
		LinkList rear;
	};

	LinkList lnode_init(LinkList lnode, ElementType data, LinkList next = NULL) {
		assert(lnode);
		lnode->data = data;
		lnode->next = next;
		return lnode;
	}

	LinkList link_create(ElementType data, LinkList next = NULL) {
		LinkList link = (LinkList)malloc(sizeof(struct LNode));
		link->data = data;
		link->next = next;
		return link;
	}

	LinkList link_free(LinkList link) {
		LinkList p = NULL;
		while (link) {
			p = link;
			free(p);
			link = link->next;
		}
		return NULL;
	}

	int queue_is_empty(Queue q) {
		if (q && q->front)
			return 0;
		return 1;
	}

	Queue queue_in(Queue q, ElementType data) {
		assert(q);
		LinkList node = link_create(data, NULL);
		if (q->front) {
			q->rear->next = node;
			q->rear = node;
		}
		else {
			q->front = q->rear = node;
		}
		return q;
	}

	ElementType queue_out(Queue q) {
		assert(q);
		if (q->front == NULL) {
			printf("队列为空");
			return ErrorData;
		}
		LinkList node = q->front;
		q->front = node->next;
		if (q->front == NULL)
			q->rear = NULL;
		ElementType data = node->data;
		free(node);
		return data;
	}

	Queue queue_init(Queue q) {
		assert(q);
		q->front = q->rear = NULL;
		return q;
	}

	Queue queue_free(Queue q) {
		assert(q);
		if (q->front)
			link_free(q->front);
		q->front = q->rear = NULL;
		return q;
	}

	int stack_is_empty(Stack s) {
		if (s && s->head && s->head->next)
			return 0;
		return 1;
	}

	Stack stack_push(Stack s, ElementType data) {
		assert(s);
		LinkList node = link_create(data, NULL);
		if (s->head == NULL)
			s->head = link_create(0, NULL);
		if (s->head->next)
			node->next = s->head->next;
		s->head->next = node;
		return s;
	}

	ElementType stack_pop(Stack s) {
		assert(s);
		if (s->head == NULL || s->head->next == NULL)
		{
			printf("空栈");
			return ErrorData;
		}
		LinkList node = s->head->next;
		s->head->next = node->next;
		ElementType data = node->data;
		free(node);
		return data;
	}

	Stack stack_free(Stack s) {
		assert(s);
		if (s->head)
			link_free(s->head);
		s->head = NULL;
		return s;
	}

	/* ---------------- 基于链表的 栈,队列 ---------------- */

	/* ---------------- 链表图 ---------------- */
	typedef int Vertex;
	typedef struct LGraphStruct* LGraph;
	struct LGraphStruct {
		int nv;
		int ne;
		struct QueueStruct* queues;
	};

	LGraph graph_init(LGraph g, int nv) {
		assert(g);
		assert(nv > 0);
		g->nv = nv;
		g->queues = (Queue)malloc(sizeof(struct QueueStruct) * nv);
		Queue queue = g->queues;
		for (int i = 0; i < nv; i++) {
			queue_init(queue++);
		}
		return g;
	}

	LGraph graph_insert_edge(LGraph g, Vertex v0, Vertex v1) {
		assert(g);
		assert(v0 >= 0);
		assert(v1 >= 0);
		queue_in(g->queues + v0, v1);
		queue_in(g->queues + v1, v0);
		return g;
	}

	const int MaxCount = 11;
	int visited[MaxCount] = {};

	void reset_visited() {
		for (int i = 0; i < MaxCount; i++)
			visited[i] = 0;
	}

	void sort_vertices(Vertex a[], int n) {
		int i, j, temp;
		for (i = 0; i < n; i++) {
			for (j = i + 1; j < n; j++) {
				if (a[j] < a[i]) {
					temp = a[j];
					a[j] = a[i];
					a[i] = temp;
				}
			}
		}
	}

	void DFS(LGraph g, Vertex v) {
		visited[v] = 1;
		printf("%d ", v);
		LinkList node = (g->queues + v)->front;
		Vertex vertices[MaxCount];
		int n = 0;
		for (; node; node = node->next) {
			if (!visited[node->data])
				vertices[n++] = node->data;
		}
		sort_vertices(vertices, n);
		for (int i = 0; i < n; i++) {
			if (!visited[vertices[i]])
				DFS(g, vertices[i]);
		}
	}

	void BFS(LGraph g, Vertex v) {
		int n;
		LinkList node = NULL;
		Vertex vertices[MaxCount];
		struct QueueStruct vertex_queue_data = {};
		Queue vertex_queue = &vertex_queue_data;
		queue_in(vertex_queue, v);

		while (!queue_is_empty(vertex_queue)) {
			v = queue_out(vertex_queue);
			if (visited[v])
				continue;

			visited[v] = 1;
			printf("%d ", v);
			node = (g->queues + v)->front;
			n = 0;
			for (; node; node = node->next) {
				if (!visited[node->data])
					vertices[n++] = node->data;
			}
			sort_vertices(vertices, n);
			for (int i = 0; i < n; i++) {
				if (!visited[vertices[i]])
					queue_in(vertex_queue, vertices[i]);
			}
		}

	}


	/* ---------------- 链表图 ---------------- */

	LGraph buildGraph(LGraph graph) {
		assert(graph);
		int nv, i;
		Vertex v0, v1;
		freopen("D:/Develop/GitRepos/MOOC/浙江大学/数据结构/201906/DataStructure/test_data/zju_e06_01.txt", "r", stdin);
		scanf("%d", &nv);
		graph = graph_init(graph, nv);
		scanf("%d", &(graph->ne));   /* 读入边数 */
		if (graph->ne > 0) {
			for (i = 0; i < graph->ne; i++) {
				scanf("%d %d", &v0, &v1);
				graph_insert_edge(graph, v0, v1);
			}
		}
		return graph;
	}

	int main() {
		LGraphStruct graph_data;
		LGraph graph = &graph_data;
		Queue queue;
		buildGraph(graph);

		reset_visited();
		queue = graph->queues;
		for (int i = 0; i < graph->nv; i++) {
			if (!visited[i]) {
				printf("{ ");
				DFS(graph, i);
				printf("}\n");
			}
		}

		reset_visited();
		queue = graph->queues;
		for (int i = 0; i < graph->nv; i++) {
			if (!visited[i]) {
				printf("{ ");
				BFS(graph, i);
				printf("}\n");
			}
		}
		return 0;
	}

}


int main_Y190713_Graph() {
	return Y190713_Graph::main();
}